package datastructure.book.dp._1_pathway.all;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class _4_Solution {

    @Test
    public void test(){
        List<List<Integer>> cntList = new ArrayList<>();
        ArrayList<Integer> oneCnt = new ArrayList<>();
        oneCnt.add(2);
        ArrayList<Integer> twoCnt = new ArrayList<>();
        twoCnt.add(3);twoCnt.add(4);
        ArrayList<Integer> threeCnt = new ArrayList<>();
        threeCnt.add(6);threeCnt.add(5);threeCnt.add(7);
        ArrayList<Integer> forCnt = new ArrayList<>();
        forCnt.add(4);forCnt.add(1);forCnt.add(8);forCnt.add(3);
        cntList.add(oneCnt);cntList.add(twoCnt);cntList.add(threeCnt);cntList.add(forCnt);
        System.out.println(minimumTotal(cntList));
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.isEmpty()) {
            return 0;
        }
        LinkedList<LinkedList<Integer>> cntList = new LinkedList<>();
        LinkedList<Integer> oneCnt = new LinkedList<>();
        oneCnt.add(triangle.get(0).get(0));
        cntList.add(oneCnt);
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> integers = triangle.get(i);
            List<Integer> preList = cntList.get(i - 1);
            LinkedList<Integer> cnt = new LinkedList<>();
            cntList.add(cnt);
            for (int j = 0; j < integers.size(); j++) {
                if (j == 0) {
                    cnt.add(integers.get(j)+preList.get(j));
                }else if (j == preList.size()){
                    cnt.add(integers.get(j)+preList.get(j-1));
                } else if (j < preList.size()){
                    cnt.add(integers.get(j)+Math.min(preList.get(j),preList.get(j - 1)));
                }
            }
        }
        LinkedList<Integer> last = cntList.getLast();
        int result = last.get(0);
        for (int i = 1; i < last.size(); i++) {
            result = Math.min(last.get(i),result);
        }
        return result;
    }
}
